#include<iostream>
#include<string>
#include<map>
#include <functional>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

void test1()
{
	string arr[] = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "苹果", "樱桃" };
	map<string, int> countMap;
	for (auto& str : arr)
	{
		map<string, int>::iterator ret = countMap.find(str);
		if (ret == countMap.end())
		{
			countMap.insert(make_pair(str, 1));
		}
		else
		{
			ret->second++;
		}
	}
	for (pair<const string, int>& node : countMap)
	{
		cout << node.first << ":" << node.second << endl;
	}
}
void test2()
{
	string arr[] = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "苹果", "樱桃" };
	map<string, int> countMap;
	for (string& str : arr)
	{
		pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
		if (ret.second == false)
		{
			ret.first->second++;
		}
	}

	for (pair<const string, int>& node : countMap)
	{
		cout << node.first << ":" << node.second << endl;
	}
}
void test3()
{
	string arr[] = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "苹果", "樱桃" };
	map<string, int> countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}

	for (pair<const string, int>& node : countMap)
	{
		cout << node.first << ":" << node.second << endl;
	}
}

void test4()
{
	map<string, string> dict;
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("left", "剩余"));//无法修改

	dict["left"] = "剩余";//修改key对应的T
	dict["test"];//插入
	cout << dict["left"] << endl;//查找

	dict["string"] = "字符串";
}

//1. 本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类
//比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果，
//并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数，并
//且求出大家最喜欢吃的前k种水果。
struct CountVal
{
	bool operator()(const pair<string, int>& l, const pair<string, int>& r)
	{
		return l.second < r.second;
	}
};

void GetFavoriteFruit(const vector<string>& fruit, size_t k)
{
	//计数
	map<string, int> countMap;
	for (const string& str : fruit)
	{
		countMap[str]++;
	}
	//数据量不大，可以用排序
	
	////法1. sort ---> 优化：将迭代器存入vector，而不是将节点存进去
	////sort排序传的迭代器必须是随机迭代器，故先将这些值放入vector
	//vector<pair<string, int>> Vsort;
	//for (auto& p: countMap)
	//{
	//	Vsort.push_back(p);
	//}
	////用sort排序
	//sort(Vsort.begin(), Vsort.end(), CountVal());//函数模板，传仿函数传的是对象
	//for (int i = 0; i < k; i++)
	//{
	//	cout << Vsort[i].first << ":" << Vsort[i].second << endl;
	//}
	
	////法2. multimap ---> 优化：将迭代器存入multimap，而不是将节点存进去
	////如multimap
	//multimap<int, string, greater<int>> sortMap;
	//for (pair<const string, int>& p : countMap)
	//{
	//	sortMap.insert(make_pair(p.second, p.first));
	//}
	//multimap<int, string>::iterator ret = sortMap.begin();
	//for (int i = 0; i < k; i++)
	//{
	//	cout << ret->second << ":" << ret->first << endl;
	//	ret++;
	//}

	//法3. priority_queue ---> 将迭代器存入priority_queue，而不是将节点存进去
	//入优先级队列
	priority_queue<pair<string, int>, vector<pair<string, int>>, CountVal> pq;
	for (pair<const string, int>& p : countMap)
	{
		pq.push(p);
	}

	for (int i = 0; i < k; i++)
	{
		cout << pq.top().first << ":" << pq.top().second << endl;
		pq.pop();
	}
}

int main()
{
	/*test1();
	test2();
	test3();
	test4();*/
	vector<string> v = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "苹果", "樱桃", "哈密瓜", "榴莲", "榴莲", "苹果" };
	GetFavoriteFruit(v, 3);
	return 0;
}